package array;

import java.util.Arrays;

/**
 * 并查集
 *
 * 每个集合有一个标志元素，用来标识集合所属的元素
 * 提供两种基本操作：
 *  1、find(int e) 返回e所属集合的标志元素，可能是自己或者集合的标志元素
 *  2、union(int e1, int e2) 将有关系的元素e1和e2合并到一个集合中，即修改e1或者e2所在结合的标志元素为对方的标志元素
 *
 */

public class UnionFindSet {

    private int[] f;

    public UnionFindSet(int size){
        f = new int[size + 1];
        init();
    }

    public void init(){
        for (int i = 1; i < f.length; i++){
            f[i] = i;
        }
    }

    public int find(int e){
        while (e != f[e])
            e = f[e];
        return e;
    }

    public int findAndChange(int e){
        if (e != f[e])
            f[e] = findAndChange(f[e]);
        return f[e];
    }

    public void union(int e1, int e2){

        int f1 = findAndChange(e1);
        int f2 = findAndChange(e2);

        // 修改某一集合的标志
        f[f2] = f1;

    }

    public boolean judge(int e1, int e2){
        return find(e1) == find(e2);
    }

    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(5);
        unionFindSet.union(1, 2);
        unionFindSet.union(2, 3);
        unionFindSet.union(3, 4);
        unionFindSet.union(5, 5);

        System.out.println("1 and 2 = " + unionFindSet.judge(1, 2));
        System.out.println("1 and 3 = " + unionFindSet.judge(1, 3));
        System.out.println("1 and 4 = " + unionFindSet.judge(1, 4));
        System.out.println("1 and 5 = " + unionFindSet.judge(1, 5));

        System.out.println("done");
    }

}
